Herein, we investigate the randomized complexity, which is the least cost against the worst input, of AND-OR tree computation by imposing various restrictions on the algorithm to find the Boolean value of the root of that tree and no restrictions on the tree shape. When a tree satisfies a certain condition regarding its symmetry, directional algorithms proposed by Saks and Wigderson (1986), special randomized algorithms, are known to achieve the randomized complexity. Furthermore, there is a known example of a tree that is so unbalanced that no directional algorithm achieves the randomized complexity (Vereshchagin 1998). In this study, we aim to identify where deviations arise between the general randomized Boolean decision tree and its special case, directional algorithms. In this paper, we show that for any AND-OR tree, randomized depth-first algorithms, which form a broader class compared with directional algorithms, have the same equilibrium as that of the directional algorithms. Thus, we get the collapse result on equilibria inequalities that holds for an arbitrary AND-OR tree. This implies that there exists a case where even depth-first algorithms cannot be the fastest, leading to the separation result on equilibria inequality. Additionally, a new algorithm is introduced as a key concept for proof of the separation result.

Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Among IDs such that probability of the root having value 0 is fixed as a given r such that 0 < r < 1, if d is a maximizer of cost of the best algorithm then d is an independent and identical distribution (IID). (2) Among all IDs, if d is a maximizer of cost of the best algorithm then d is an IID. In the case where non-depth-first algorithms are taken into consideration, the counter parts of (1) and (2) are left open in the above work. Peng et al. (Inform. Process. Lett., 2017) extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on IDs that probability of the root having value 0 is neither 0 nor 1. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID d achieves the equilibrium among IDs then we can chose an algorithm of the best cost against d from depth-first algorithms. In addition, we extend the result of Peng et al. to the case where non-depth-first algorithms are taken into consideration.